/**
 * 
 */
package problem;

import java.util.ArrayList;
import java.util.List;

import datastructure.Stack;
import datastructure.impl.SeqStack;

/**
 * @author Jun
 *
 */
public class MazeSolve {

	private List<DataElem> result;
	
	private int pos;	
	
	public MazeSolve(){
		
		result = new ArrayList<DataElem>();
		pos = -1;
		
	}
	
	
	/**
	 * Data model: 
	 * 		Maze int[][], 0 through; 1 wall; 2 mark
	 * 		element in stack:	int x, y, d
	 * 		direction[4][2]:
	 * 			E 0: 0, 1	 	S 1: 1,0
	 * 			W 2: 0,-1		N 3: -1,0 
	 * 				
	 * 
	 * /
	
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	
	public boolean Solve1(int[][] maze, int[][] direction, int x1, int y1, int x2, int y2){
		
	
		// start point
		DataElem de1 = new DataElem(x1,y1,-1);		
		result.add(de1);
		pos++;
		
		if(x1==x2 && y1==y2)
			return true;
		
		int g = 0;
		int h = 0;
		
		DataElem tmp = null;
		boolean solved = false;
		
		for(int i=0; i< direction.length; i++){
			
			g = de1.x + direction[i][0];
			h = de1.y = direction[i][1];
			
			//该点不通
			if(maze[g][h]==1) continue;
//			tmp = new DataElem(g,h,-1);
//			result.add(tmp);			
//			pos++;			
			
			solved = Solve1(maze, direction, g, h, x2, y2);
			if(solved) break;	
			// backtrack
			pos--;			
			
		}
		
		return solved;
	}
	
	public boolean Solve2(int[][] maze, int[][] direction, int x1, int y1, int x2, int y2){
		
		Stack<DataElem> pstack = new SeqStack<DataElem>(DataElem.class);
		maze[x1][y1] = 2;
		DataElem elem = new DataElem(x1,y2,-1);
		pstack.push(elem);
		
		int i = 0;
		int j = 0;
		int k = 0;
		int g = 0;
		int h = 0;
		
		while(!pstack.isEmptyStack()){
			elem = pstack.top();
			i = elem.x;
			j = elem.y;
			k = elem.d+1;
			while(k<=3){		//依次试探各个方向
				
				g = i + direction[k][0];
				h = j + direction[k][1];
				
				if(g== x2&& h == y2 && maze[g][h] ==0){ //走到出口点
					
					System.out.println("print routine");
				}
				else if (maze[g][h]==0) {	//走到没走过的点
					maze[g][h] = 2;			//做标记
					elem = new DataElem(g,h,-1);	
					pstack.push(elem);	//进栈
					
					//下一结点转换为当前点
					k = -1;
					i = g;
					j = h;

				}
			}
			
			
		}
		
		
		return false;
	}
	
	
	public void print(Stack<DataElem> pstack){
		
		if(pstack.isEmptyStack())	return;
		DataElem tmp = pstack.top();
		pstack.pop();
		print(pstack);
		System.out.println(tmp+" ");
		
	}

}

class DataElem{
	
	public DataElem(int x, int y, int d) {
		super();
		this.x = x;
		this.y = y;
		this.d = d;
	}
	int x;
	int y;
	int d;
	
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return String.format("[%s,%s]", x,y);
	}
	
	
	
	
}
